package com.chj.leetcode.tijie1450to1500;

public class Code1473_PaintHouseIII {
	public int minCost(int[] hs, int[][] cost, int m, int n, int target) {
		int INF = Integer.MAX_VALUE;
		int[][][] f = new int[m][target + 1][n + 1];

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < target + 1; j++) {
				for (int k = 0; k < n + 1; k++) {
					f[i][j][k] = INF;
				}
			}
		}

		if (hs[0] > 0) {
			f[0][1][hs[0]] = 0;

		} else {
			for (int i = 1; i <= n; i++) {
				f[0][1][i] = cost[0][i - 1];
			}
		}

		for (int i = 1; i < m; i++)
			for (int j = 1; j <= target; j++) {
				if (hs[i] > 0) {
					int k = hs[i];

					for (int u = 1; u <= n; u++) {
						if (u == k) {
							f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][u]);

						} else {
							f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][u]);
						}
					}

				} else {
					for (int k = 1; k <= n; k++) {
						for (int u = 1; u <= n; u++) {
							if (u == k) {
								if (f[i - 1][j][u] == INF) {
									continue;
								}
								f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][u] + cost[i][k - 1]);

							} else {
								if (f[i - 1][j - 1][u] == INF) {
									continue;
								}
								f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j - 1][u] + cost[i][k - 1]);
							}
						}
					}
				}
			}

		int res = INF;
		for (int i = 1; i <= n; i++) {
			res = Math.min(res, f[m - 1][target][i]);
		}
		if (res == INF) {
			res = -1;
		}

		return res;
	}
// https://www.acwing.com/solution/content/14381/
//	作者：yxc
//	链接：https://www.acwing.com/activity/content/code/content/339214/
//	来源：AcWing
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
